'''
难度 中等
题目链接 https://leetcode.cn/problems/h-index-ii/description/
'''

from typing import List


class Solution:
    # 利用二分
    def hIndex(self, citations: List[int]) -> int:
        begin, end, n = 0, len(citations) - 1, len(citations)
        
        while begin <= end:
            mid = begin + (end - begin) // 2
            if citations[mid] > n - mid:
                end = mid -1
            elif citations[mid] < n - mid:
                begin = mid + 1
            else:
                return citations[mid]

        return n - begin
    

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [[0,1,3,5,6]],
        [[1,2,100]],
        [[0]],
    ]
    预期 = [
        3,
        2,
        1,
    ]
    for k,v in enumerate(参数):
        r = s.hIndex(v[0])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))